#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 162. 寻找峰值.py
@time: 2022/1/29 17:01
@desc: https://leetcode-cn.com/problems/find-peak-element/
峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

@解题思路：
    1. 二分, Ot(logN), Os(1)
    2. 直接找最大值, Ot(N), Os(1)
'''

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n==1: return 0
        def bs(left, right):
            if left<=right:
                mid = (left+right)//2
                if mid == 0 and mid<n-1 and nums[mid]>nums[mid+1]: return mid
                elif mid==n-1 and mid>0 and nums[mid]>nums[mid-1]: return mid
                elif nums[mid-1]<nums[mid]>nums[mid+1]: return mid
                else:
                    res = bs(left, mid-1)
                    if not res==-1: return res
                    res = bs(mid+1, right)
                    if not res==-1: return res
            return -1
        return bs(0, n-1)

# 直接最大值
class Solution02(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        idx = 0
        for i in range(n):
            idx = i if nums[i]>nums[idx] else idx
        return idx

if __name__ == '__main__':
    res = Solution().findPeakElement([6,5,4,3,2,3,2])
    print(res)